package org.aplombh.java.awcing.basic.dp.linearDP;

import java.io.*;
import java.util.ArrayList;

/**
 * 给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
 * <p>
 * 删除–将字符串 A 中的某个字符删除。
 * 插入–在字符串 A 的某个位置插入某个字符。
 * 替换–将字符串 A 中的某个字符替换为另一个字符。
 * 现在请你求出，将 A 变为 B 至少需要进行多少次操作。
 * <p>
 * 输入格式
 * 第一行包含整数 n，表示字符串 A 的长度。
 * <p>
 * 第二行包含一个长度为 n 的字符串 A。
 * <p>
 * 第三行包含整数 m，表示字符串 B 的长度。
 * <p>
 * 第四行包含一个长度为 m 的字符串 B。
 * <p>
 * 字符串中均只包含大小写字母。
 * <p>
 * 输出格式
 * 输出一个整数，表示最少操作次数。
 * <p>
 * 数据范围
 * 1≤n,m≤1000
 * 输入样例：
 * 10
 * AGTCTGACGC
 * 11
 * AGTAAGTAGGC
 * 输出样例：
 * 4
 */
public class MinimumEditDistance_902 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String a = reader.readLine();
        int m = Integer.parseInt(reader.readLine().trim());
        String b = reader.readLine();
        MinimumEditDistance med = new MinimumEditDistance();
        System.out.println(med.solve(a, b));
    }
}

class MinimumEditDistance {
    public static final int N = 1010;
    int[][] f = new int[N][N];
    char[][] path = new char[N][N];
    int n, m;

    public int solve(String a, String b) {
        char[] x = a.toCharArray();
        char[] y = b.toCharArray();
        n = a.length();
        m = b.length();

        for (int i = 0; i <= n; i++) {
            // 初始化 最多i步 -> 全部删除
            f[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {
            // 初始化 最多i步 -> 全部新增
            f[0][i] = i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 删掉x[i]或删掉x[j]
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (f[i - 1][j] < f[i][j - 1]) {
                    // x删掉x[i]
                    path[i][j] = 'd';
                } else {
                    // x添加y[j]
                    path[i][j] = 'a';
                }

                // 如果相同就不用调整,值和f[i-1][j-1]相同
                if (x[i - 1] == y[j - 1]) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                    if (f[i][j] < f[i - 1][j - 1]) {
                        // 上面情况比f[i-1][j-1]快,不用变
                        path[i][j] = path[i][j];
                    } else {
                        // f[i-1][j-1]比上面情况快
                        path[i][j] = 'n';
                    }
                }
                // 否则从两字符串上一个位置调整,替换
                else {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                    if (f[i][j] < f[i - 1][j - 1] + 1) {
                        // 上面情况比f[i-1][j-1]快,不用变
                        path[i][j] = path[i][j];
                    } else {
                        // f[i-1][j-1]+1比上面情况快,替换
                        path[i][j] = 'r';
                    }
                }
            }
        }

        // path
        ArrayList<String> str = new ArrayList<>();
        for (int i = n, j = m; i > 0; ) {
            switch (path[i][j]) {
                case 'd': {
                    str.add("del: " + i + "th digit " + x[i - 1]);
                    i--;
                    break;
                }
                case 'a': {
                    str.add("add: " + i + "th digit " + y[j - 1]);
                    j--;
                    break;
                }
                case 'n': {
                    i--;
                    j--;
                    break;
                }
                case 'r': {
                    str.add("replace: " + i + "th digit " + x[i - 1] + " to " + y[j - 1]);
                    i--;
                    j--;
                }
            }
        }
        for (int k = str.size() - 1; k >= 0; k--) {
            System.out.println(str.get(k));
        }

        return f[n][m];
    }

}
